//    En esta clase se define un algoritmo genetico que  dependiendo de como se aplican los
//    operadores de cruza, mutacion,replicacion y de como se realiza la seleccion de aptitud(elitista)
//    generan nuevas poblaciones que puede dar el resultado al problema.

package mx.unam.ia.algoritmos;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;

/**
 *
 * @author Juan Fco. Navarrete
 */


//   Al iniciar el Algoritmo genetico: se obtienen los cromosomas y se evaluan (para verificar aptitud),
//   despues se seleccionan dependiendo su aptitud, se cruzan y mutan para poder obtener
//   una nueva poblacion (generaciones).  Los cromosomas con mejor aptitud tienen
//    mayor probabilidad de ser seleccionados. .

public class AlgoritmoGenetico
{

    private Cromosoma[] cromosomas;
    private int generaciones;
    private double cruza;
    private double mutacion;    
    private int elitista;
    private int poblacion;
    private EvaluadorCromosomas evaluador;
    private GeneradorCromosomas generador;
    private StringBuilder sb = new StringBuilder();

    public AlgoritmoGenetico(GeneradorCromosomas generador, EvaluadorCromosomas evaluador, int poblacion, int generaciones, double cruza, double mutacion, double porcentajeElitista)
    {
        this.generador = generador;
        this.evaluador = evaluador;
        this.generaciones = generaciones;
        this.cruza = cruza;
        this.poblacion = poblacion;
        this.mutacion = mutacion;
        this.elitista = (int) ((poblacion) * (porcentajeElitista / 100));        
    }

    private void generarPoblacion() //Funcion que genera la poblacion en base a los cromosomas
    {
        cromosomas = generador.generarCromosomas(poblacion);
    }

    private void evaluarCromosomas() //Cada cromosoma es evaludado y después acomodado según su aptitud.
    {        
        for (int i = 0; i < cromosomas.length; i++)
        {
            evaluador.evaluarCromosoma(cromosomas[i]);            
        }                
        Arrays.sort(cromosomas);
    }

    public void obtenerPoblacion() //Se obtiene la nueva porblación de los cromosomas
    {        
        for (int i = 0; i < cromosomas.length; i++)
        {
            sb.append((i + 1) + ":\t" + cromosomas[i].toString() + "\n");
        }        
    }


    //Para seleccionar individuos y que los mejores tengan mas posibilidades de ser seleccionados.
    //Se puede desplazar hacia la izquierda  o hacia la derecha del cromosoma.

    public double[] crearRuleta()
    {
        double suma = 0;
        for (int i = 0; i < cromosomas.length; i++)
        {
            suma +=cromosomas[i].getEvaluacion();
        }
        double[] probabilidades = new double[cromosomas.length];        
        double suma2 = 0;
        for (int i = 0; i < probabilidades.length; i++)
        {
            probabilidades[i] = suma/cromosomas[i].getEvaluacion();
            suma2 += probabilidades[i];
        }                
        double[] ruleta = new double[probabilidades.length];
        suma = 0;
        for (int j = probabilidades.length - 1; j >= 0; j--)
        {
            ruleta[j] = probabilidades[j]/suma2 + suma;
            suma += probabilidades[j]/suma2;
        }
        ruleta[0] = 1;
        return ruleta;
    }

    //Permite seleccionar un número aleatorio que este dentro del rango permitido (por lo que
    //se compara con el valor de la ruleta, en caso que no sea valido, mostrará el error.
    private int seleccionar(double[] ruleta)
    {
        double aleatorio = Math.random();
        for (int i = ruleta.length - 1; i >= 0; i--)
        {
            if(aleatorio < ruleta[i])
                return i;
        }
        throw new UnsupportedOperationException("Error al utilizar la ruleta");        
    }



//    Despues de saber la aptitud de cada cromosoma se procede a elegir los cromosomas
//    que seran cruzados en la siguiente generacion.
//    A cada uno de estos individuos se les aplican los operadores geneticos de cruza
//    siempre y cuando  se genere un numero aleatorio menor que la cruza. También se aplica la
//    mutacion para cada valor aleatorio menor que la mutacion  para conformar la
//    poblacion de la generacion siguiente.

    private void evolucionar()
    {
        double[] ruleta = crearRuleta();
        Cromosoma[] tmp = new Cromosoma[cromosomas.length];
        for (int i = 0; i < elitista; i++)
        {            
            tmp[i] = cromosomas[i];
        }
        for (int i = elitista; i < cromosomas.length;)
        {
            if(Math.random() < cruza)
            {
                int indiceX = seleccionar(ruleta);
                int indiceY = seleccionar(ruleta);
                Cromosoma x = new Cromosoma(cromosomas[indiceX].getExpresion());
                Cromosoma y = new Cromosoma(cromosomas[indiceY].getExpresion());
                cruzar(x, y);                
                tmp[i++] = x;                
                if(i < cromosomas.length - 1)
                    tmp[i++] = y;                
            }
            else
            {
                int indiceX = seleccionar(ruleta);
                Cromosoma x = new Cromosoma(cromosomas[indiceX].getExpresion());
                tmp[i++] = x;                                
            }
        } 
        for (int i = elitista; i < cromosomas.length; i++)
        {
            if(Math.random() < mutacion)
            {
                mutar(tmp[i]);
            }
        }
        cromosomas = tmp;        
    }

//   Se modifica al azar parte del cromosoma de los individuos: se genera un numero aleatorio, si 
//   cae dentro de la probabilidad de mutacion entonces genera un numero aleatorio para definir
//   el punto donde se mutara: si se trata de una funcion, lo hara por otra funcion ya sea binaria
//   o unaria si se trata de un terminal por otro terminal. Esto se realizara siempre y cuando 
//   se reconozca el simbolo.
    private void mutar(Cromosoma x)
    {
        int indice = (int) (Math.random() * x.getExpresion().length());
        StringBuilder sbX = new StringBuilder(x.getExpresion());
        String nuevo = null;
        if (indice < generador.getCabeza())
        {
            double aleatorio = Math.random();
            if (aleatorio < generador.getProbabilidadOperacion())
            {
                if (aleatorio < (generador.getProbabilidadOperacion() / 2))
                    nuevo = OperacionUnaria.obtenerOperacion();
                else
                    nuevo = OperacionBinaria.obtenerOperacion();
            }
            else
                nuevo = Terminal.obtenerTerminal();
        }
        else
            nuevo = Terminal.obtenerTerminal();
        sbX.setCharAt(indice, nuevo.charAt(0));
        x.setExpresion(sbX.toString());
    }

//    Genera un numero aleatorio, para cada individuo  X y Y que se cruzara para indicar
//    el punto donde se cruzaran.
//    Al cruzarlos se generan dos nuevos individuos para la siguiente generacion.
    private void cruzar(Cromosoma x, Cromosoma y)
    {
        int indice = (int) (Math.random() * x.getExpresion().length() - 1);
        StringBuilder sbX = new StringBuilder(x.getExpresion());
        StringBuilder sbY = new StringBuilder(y.getExpresion());
        String inicioX = sbX.substring(0, indice + 1);
        String inicioY = sbY.substring(0, indice + 1);
        sbX.replace(0, indice + 1, inicioY);
        sbY.replace(0, indice + 1, inicioX);
        x.setExpresion(sbX.toString());
        y.setExpresion(sbY.toString());
    }


    public Cromosoma ejecutar()
    {
        generarPoblacion();
        evaluarCromosomas();
        sb.append("********Poblacion Inicial********\n");
        obtenerPoblacion();        //Se obtiene la población inicial
        for (int i = 0; i < generaciones; i++)
        {
            evolucionar();
            evaluarCromosomas();
            if(i<5 || i > generaciones - 5)
            {                
                sb.append("********Poblacion " + i + "********\n");
                obtenerPoblacion(); //Se obtiene la poblacion que va siendo modificada, el ciclo se repite hasta que se cumplan las generaciones dadas.
            }
        }                
        return cromosomas[0];
    }

    public StringBuilder getSb() //se declara el constructor de cadena
    {
        return sb;
    }

    public void setSb(StringBuilder sb) //Función que establece el constructor de cadena
    {
        this.sb = sb;
    }


//  Se establecen los parametros dados.
//  50 generaciones
//  25 individuos en la poblacion
//  0.5 probabilidad de cruza
//  0.2 probabilidad de mutacion
//  Porcentaje de poblacion para seleccion elitista 20%
    public static void main(String[] args)
    {
        double x[] =
            {
                -2.8577, -2.8533, -2.1226, -1.8784, -1.3373, -1.278, -0.7809, -0.7196, -0.38318, -0.1837, -0.1406, 0.0253, 0.0621, 0.5572, 0.6630, 0.9391, 0.9413, 1.4329, 1.4348, 1.4531, 1.4964, 1.5106, 1.6081, 1.6676, 1.7334, 2.0301, 2.2076, 2.2206, 2.5794, 2.6919, 2.9618, 3.6405, 4.0368, 4.0847, 4.1335, 4.1812, 4.2198, 4.2406, 4.5948, 4.8386, 5.0452, 5.1621, 5.2886, 5.5184, 6.0282, 6.3290, 6.4976, 6.6882, 6.7709, 6.8616
            };
            double y[] =
            {
                12.5108, 12.6057, 9.6063, 7.1904, 2.4157, 1.9671, -1.0743, -1.3543, -2.4974, -2.845, -2.8885, -0.9478, -0.9367, 0.1179, 0.561, 2.0746, 2.0888, 6.0671, 6.086, 6.2655, 6.7014, 6.8468, 7.8851, 8.5533, 9.3218, 13.216, 15.9383, 16.1525, 23.2309, 26.2879, 40.98, 29.164, 39.8053, 40.9746, 42.1587, 43.3093, 44.2364, 44.7361, 53.2323, 59.132, 64.1467, 66.9617, 69.9539, 75.0719, 75.2065, 247.6863, 145.9792, 139.4597, 140.0652, 141.6499
            };
        double aleatorio = Math.random();        
        EvaluadorCromosomas evaluador = new EvaluadorCromosomas(1.0, x, y);
        GeneradorCromosomas generador = new GeneradorCromosomas(15, 2, 0.95);
        AlgoritmoGenetico genetico = new AlgoritmoGenetico(generador, evaluador, 25, 50, 0.5, 0.3, 15);
        Cromosoma solucion = genetico.ejecutar();
        double promedio = solucion.getEvaluacion();
        for (int i = 0; i < 0; i++)
        {
            Cromosoma tmp = genetico.ejecutar();
            promedio += tmp.getEvaluacion();
            if(tmp.getEvaluacion() < solucion.getEvaluacion())
                solucion = tmp;
        }
        System.out.println(genetico.getSb());
               
        //Se imprime el número aleatorio, la evaluación del mejor individuo, su expresión y el recorrido del arbol.
        System.out.println("Numero Aleatorio : " + aleatorio);
        System.out.println("Evaluacion mejor individuo: " + solucion.getEvaluacion());
        System.out.println("Expresion mejor invidivuo: " + solucion.getExpresion());
        System.out.println("Recorrido en orden del mejor individuo: " + solucion.getArbol().enOrden());
        System.out.println("PROMEDIO " + (promedio/100));
    }

}